﻿//https://leetcode.cn/problems/monotone-increasing-digits/

class Solution {
public:
    int monotoneIncreasingDigits(int n)
    {
        string s = to_string(n);

        //找到最后一个单调递增的数字
        int i = 0;
        while (i + 1 < n && s[i] <= s[i + 1]) i++;

        if (i + 1 == s.size()) return n;

        //找到最后一个单调递增的相同的数字的最开端
        int j = i;
        while (j - 1 >= 0 && s[j] == s[j - 1]) j--;

        s[j]--;
        for (int k = j + 1; k < s.size(); k++)
        {
            s[k] = '9';
        }

        return stoi(s);

    }
};